#include "../tools.h"


class Solution {
public:
    void DFS(vector<vector<char>>& grid, int r, int c, int n_r, int n_c){
        grid[r][c] = '0';

        // 选择 - 递归：注意如何区分已选路径、可选路径
        if(r - 1 >= 0 && grid[r - 1][c] == '1') DFS(grid, r - 1, c, n_r, n_c);
        if(r + 1 < n_r && grid[r + 1][c] == '1') DFS(grid, r + 1, c, n_r, n_c);
        if(c - 1 >= 0 && grid[r][c - 1] == '1') DFS(grid, r, c - 1, n_r, n_c);
        if(c + 1 < n_c && grid[r][c + 1] == '1') DFS(grid, r, c + 1, n_r, n_c);

    }

    int numIslands(vector<vector<char>>& grid) {
        int res = 0;

        int n_r = grid.size(), n_c = grid[0].size();
        for(int r = 0; r < n_r; ++r){
            for(int c = 0; c < n_c; ++c){
                if(grid[r][c] == '1'){
                    // cout << r << "-" << c << endl;
                    DFS(grid, r, c, n_r, n_c);
                    ++res;
                }
            }
        }
        return res;
    }
};


int main(int argc, char const *argv[])
{
    // vector<vector<char>> grid = {
    //     {'1', '1', '1', '1', '0'},
    //     {'1', '1', '0', '1', '0'},
    //     {'1', '1', '0', '0', '0'},
    //     {'0', '0', '0', '0', '0'}
    // };

    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };

    Solution s;

    cout << s.numIslands(grid) << endl;

    return 0;
}
